package com.linwen.excise.sort;

/**
 * @author : linwen
 * @date : 下午10:39 2021/6/8
 */
public class _06QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{-4,2,5,4,7,8,9,-9,99};
        quickSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"  ");
        }
    }

    private static void quickSort(int[] arr) {
        quickSort(arr,0,arr.length-1);
    }

    private static void quickSort(int[] arr, int left, int right) {
        if(left<right){
            int mid = quickSort(arr,left,right-1, right);
            quickSort(arr,left,mid-1);
            quickSort(arr,mid+1,right);
        }
    }

    private static int quickSort(int[] arr, int left, int right, int flag) {
        for (int i = left+1; i <= right; i++) {
            if(arr[i]<arr[flag]){
                Sortutil.swap(arr,i,left);
                left++;
            }else if(arr[i]>arr[flag]){
                Sortutil.swap(arr,i,right);
                right--;
            }
        }
        return left;
    }

}
